The invention generally relates to digital communication and in particular to methods, systems, and computer program products for sequentially decoding a received data signal.
Over the past decades, major advances have been achieved to deploy wireless communication systems providing different types of communication. Wireless communication systems provide users access to one or more resources (e.g., bandwidth, transmit power, etc.). Different wireless communication systems are available today, such as the cellular and wireless ad-hoc networks accommodating single or multiple transmitters/receivers using single or multiple antennas, such as MIMO (Multiple Input-Multiple Output) systems.
In addition to low-power consumption and memory requirements imposed by the system devices, a major challenge of wireless communication systems is the decoding of the received signals. Indeed, in a wireless communication system, the signals transmitted to one or more receivers are conveyed in a transmission channel which may be noisy. The signals received by a receiver can thus be disturbed. A decoder is thus required to decode the original desired signal correctly.
Optimal decoding methods are based on a decoding problem known as the “Maximum Likelihood” decoding problem (also called “ML” decoding) to estimate the closest vector to the observed received signal under the minimization of an Euclidean distance criterion. One implementation of the ML decoding criterion uses an exhaustive search over all the possible values in the constellation alphabet. This method provides optimal performance. However, it requires a high complexity that increases as the size of the constellation codebook or the number of the transmit antennas becomes higher, thereby making the implementation of such techniques impossible in practical systems. The implementation of such ML decoding techniques is thus impossible in practical systems requiring a high constellation order to guarantee a high spectral efficiency as well as an increasing number of antennas for ensuring a higher diversity order.
Other ML criterion-based decoding techniques have been proposed to properly decode the received signal while considering the decoder complexity, such as the Sphere Decoder (E. Viterbo and J. Boutros. A universal lattice code decoder for fading channels. IEEE Transactions on Information Theory, 45(5):1639-1642, July 1999) or the Schnorr-Euchner decoder (C. P. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. In Math. Programming, pages 181-191, 1993). However, these decoders have an increasing complexity as the constellation size or the number of antennas increases. Other suboptimal low-complexity decoders, such as the ZF (Zero-Forcing), the ZF-DFE (Zero Forcing-Decision Feedback Equalizer) and the MMSE (Minimum Mean Square Error) detector are implemented in practical systems but present poor performances in terms of the achievable diversity order and so on error performance.
Still other decoding algorithms applicable in linear communication systems, using single or multiple users and/or antennas, include the lattice sequential decoders (such as the “stack” decoder) which implement the optimal ML detection (also referred to as ‘decoding’) criterion using a tree representation of the ML optimization problem (decoding tree) and a tree search. Such decoding algorithms provide a reduced complexity with respect to the exhaustive search approach. In the decoding tree, each path from the root node to a leaf node is a possible transmitted signal. Nodes in the decoding tree correspond to different values taken by the decoded symbols and each path from the root node to a leaf node is a possible transmitted signal. According to the search strategy implemented by sequential decoders, the expanded tree nodes are stored in a global stack. In particular, the stack decoder stores, in the global stack, the tree nodes expanded during the decoding process and sort them according to an increasing order of their decoding metrics.
Sequential decoders include decoders implementing a Best-First tree search such as the Stack decoder as disclosed in:    A. R. Murugan, H. El-Gamal, M.-O. Damen, and G. Caire. A unified framework for tree search decoding: Rediscovering the sequential decoder. IEEE Transactions on Information Theory, 52(3):933-953, March 2006;    F. Jelinek. Fast sequential decoding algorithm using a stack. IBM J. Res. Dev., 13(6):675-685, November 1969.
Another type of lattice sequential decoding method using a Best-First tree search is known as the Fano decoding method as disclosed in R. Fano. A heuristic discussion of probabilistic decoding. IEEE Transactions on Information Theory, 9(2):64-74, April 1963.
Sequential decoders improve the overall decoding complexity. However, for an increasing constellation size and a high number of antennas, the stack decoding technique requires a high computational complexity. In order to reduce this complexity, another decoding technique referred to as the Spherical-Bound Stack decoder (SB-Stack) has been proposed in the article by G. R. Ben-Othman, R. Ouertani, and A. Salah, entitled “The Spherical Bound Stack Decoder”, In Proceedings of International Conference on Wireless and Mobile Computing, pages 322-327, October 2008. The SB-stack approach combines the Stack search strategy with the Sphere Decoder search region: the decoder searches for the closest vector inside a sphere centered at the received point implementing the stack decoding strategy. The spherical search region imposes a search interval for each detected symbol. Only nodes belonging to these intervals at each tree level are visited and expanded.
Lattice sequential decoders have strongly imposed themselves as optimal detection schemes in linear wireless communication systems reducing the optimal ML decoding problem to the search for the path in a graph-tree having the least cumulated metric.
In a conventional sequential decoder, to determine a best fit (path), a value is assigned to each node in the tree. This value is called the metric which is given by (8).
In some conventional approaches, the path metric for each node at a given level k of the decoding tree may be reduced of a term “b×k” which depends on a bias term b and on the level k.
The bias term allows controlling the amount of computations performed by the decoder. Also, the bias term makes it possible to achieve a plethora of performance-complexity tradeoffs of the decoder.
With the introduction of a bias term b in the ML metric, parameterized sequential decoders including the Stack, Fano and SB-Stack decoders, offer a flexibility in terms of performance-complexity tradeoffs. The selection of the bias in spatially multiplexed and coded MIMO systems is generally fixed deterministically without taking into account the channel statistics or the noise level. In other approaches using convolutional codes, such as the approach disclosed in R. Fano. A heuristic discussion of probabilistic decoding. IEEE Transactions on Information Theory, 9(2):64-74, April 1963, an optimized value for the bias is defined which corresponds to the coding rate of the underlying code. For convolutional lattice coding joint to Tomlinson-Harashima shaping, as described in O. Shalvi, N. Sommer, and M. Feder, Signal codes: Convolutional lattice codes, IEEE Transactions on Information Theory, 57(8):5203-5226, August 2011, the optimized value of the bias for high (Signal-to-Noise Ratio) SNR regime is defined as
            :        ⁢          b      adap        =            σ      2        ⁢          log      ⁡              (                  4                      πσ            2                          )            where σ2 designates the variance of the additive noise.
However, in the existing approaches, the bias parameter is set up uniformly, whatever the selection criterion of the bias parameter is, for all the levels of the decoding tree. In other words, the value of the bias parameter is the same for all the tree levels, which results in an insufficient flexibility in terms of performance/complexity.